/**
 * 删除有序数组中的重复项
 *
 * 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
 * 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
 * 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
 * 返回 k 。
 * 判题标准:
 * 系统会用下面的代码来测试你的题解:
 * int[] nums = [...]; // 输入数组
 * int[] expectedNums = [...]; // 长度正确的期望答案
 * int k = removeDuplicates(nums); // 调用
 * assert k == expectedNums.length;
 * for (int i = 0; i < k; i++) {
 *     assert nums[i] == expectedNums[i];
 * }
 * 如果所有断言都通过，那么您的题解将被 通过。
 *
 * 示例 1：
 * 输入：nums = [1,1,2]
 * 输出：2, nums = [1,2,_]
 * 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
 *
 * 示例 2：
 * 输入：nums = [0,0,1,1,1,2,2,3,3,4]
 * 输出：5, nums = [0,1,2,3,4]
 * 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
 */

/**
 * 1.这题用常规手段很简单, 就不说了, 先说个我觉的时间复杂最快的,
 * 我们只需要遍历一遍数组就可以了, 在遍历的时候记录上一个数, 并于后面的数作比较
 * 如果相同就跳过, 不相同就将其放到对应的位置, 所以我们需要声明一个数来记录这个位置
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 *
 * 2.这个方法看代码就感觉高级一点, 其实说内在的也没有高级很多, 时间复杂度还要多出不少
 * 我们一个一个的判断, 如果遇到相等的数, 就将整体向前面移动一个数, 然后继续判断
 * 时间复杂度 : O(n^2)
 * 空间复杂度 : O(1)
 */

public class Main {

    // 1. 时间复杂度最快的
    public int removeDuplicates1(int[] nums) {

        // tmp : 用作比较是否和前面的数相同的打工仔
        // n : 记录有多少个不同的数
        // 因为第一个数肯定是不同于其他的数的, 所以从第二个数开始判断
        int tmp = nums[0], n = 1;

        // 开始从第二个数进行判断
        for (int i = 1; i < nums.length; i++) {

            // 如果于前面的数相同就跳过它, 注意在循环里面循环要注意数组越界
            while (i < nums.length && tmp == nums[i]) {
                i++;
            }

            // 要是最后一个数与前面一样, 肯定会走到数组越界, 所以我们也要在这判断下是否已经超过数组长度
            if (i == nums.length) {
                break;
            }

            // 将记录的数换一个
            tmp = nums[i];

            // 并赋值到前面对应的位置
            nums[n] = tmp;

            // 并使这个数 + 1
            n++;
        }
        return n;
    }


    // **************************************************
    // 2.
    public int removeDuplicates(int[] nums) {

        // nums 的长度
        int n = nums.length;

        // 从一开是开始遍历
        int i = 0;
        // 注意因为我们需要后面一个数来进行比较, 所以在定义范围的时候要在 nums长度 减 1, 避免越界
        while (i < n - 1) {

            // 相等个的或要将后面的数整体向前移动一个单位
            if (nums[i] == nums[i + 1]) {

                // 移动一个单位
                for (int j = i + 1; j < n - 1; j++) {
                    nums[j] = nums[j + 1];
                }

                // 因为排除一个数, 所以将总长度减一
                n--;
                continue;
            }

            // 不相等就向后遍历
            i++;
        }

        // 因为有多少个相同的数就排除了多少个数, 所以 n 就是最后不相同的数的个数
        return n;
    }
}